import time

N = 1000000
is_prime = [0] * (N + 1)

'''
素数筛法：
'''


def sieve():
    for i in range(0, N + 1):  is_prime[i] = True
    is_prime[0] = is_prime[1] = False
    for p in range(2, N):
        if p * p > N:
            break
        if is_prime[p]:
            for i in range(p * 2, N + 1, p):
                is_prime[i] = False


# 验证哥德巴赫猜想，对于大于6的每一个偶数n都可以分解成两个素数p,q，满足 p+q=n 约定p<=q O(N^2.5)
def goldbach(N):
    for n in range(6, N + 1, 2):
        flag = False  # 先假设n不能分解成两个素数
        for p in range(3, n, 2):
            q = n - p
            if p > q: break
            if is_prime[p] and is_prime[q] and p + q == n:
                flag = True  # n确实可以分解成素数p,q
                break
        if not flag:
            print(n, flag)
    # print('Bye!!')


sieve()
for k in range(1, 7):
    n = 10 ** k
    start = time.time()
    goldbach(n)
    end = time.time()
    print(f"T({n})={end - start}")
